0911. 在线选举【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 预处理 + 二分查找

1. 📝 题目描述

• leetcode

给你两个整数数组 persons 和 times。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

• TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
• int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例：

输入：
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
输出：
[null, 0, 1, 1, 0, 0, 1]

解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0，在时刻 3，票数分布为 [0]，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1，在时刻 12，票数分布为 [0,1,1]，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1，在时刻 25，票数分布为 [0,1,1,0,0,1]，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1

---

提示：

• 1 <= persons.length <= 5000
• times.length == persons.length
• 0 <= persons[i] < persons.length
• 0 <= times[i] <= 10^9
• times 是一个严格递增的有序数组
• times[0] <= t <= 10^9
• 每个测试用例最多调用 10^4 次 q

2. 🎯 s.1 - 预处理 + 二分查找

c

typedef struct {
    int* times;
    int* leaders;
    int size;
} TopVotedCandidate;

TopVotedCandidate* topVotedCandidateCreate(int* persons, int personsSize, int* times, int timesSize) {
    TopVotedCandidate* obj = (TopVotedCandidate*)malloc(sizeof(TopVotedCandidate));
    obj->size = personsSize;
    obj->times = (int*)malloc(sizeof(int) * personsSize);
    obj->leaders = (int*)malloc(sizeof(int) * personsSize);
    memcpy(obj->times, times, sizeof(int) * personsSize);
    int votes[5001];
    memset(votes, 0, sizeof(votes));
    int lead = -1, leadVotes = 0;
    for (int i = 0; i < personsSize; i++) {
        votes[persons[i]]++;
        if (votes[persons[i]] >= leadVotes) { lead = persons[i]; leadVotes = votes[persons[i]]; }
        obj->leaders[i] = lead;
    }
    return obj;
}

int topVotedCandidateQ(TopVotedCandidate* obj, int t) {
    int lo = 0, hi = obj->size - 1;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (obj->times[mid] <= t) lo = mid; else hi = mid - 1;
    }
    return obj->leaders[lo];
}

void topVotedCandidateFree(TopVotedCandidate* obj) { free(obj->times); free(obj->leaders); free(obj); }

js

/**
 * @param {number[]} persons
 * @param {number[]} times
 */
var TopVotedCandidate = function (persons, times) {
  this.times = times
  this.leaders = []
  const votes = new Map()
  let lead = -1
  for (let i = 0; i < persons.length; i++) {
    votes.set(persons[i], (votes.get(persons[i]) || 0) + 1)
    if (votes.get(persons[i]) >= (votes.get(lead) || 0)) lead = persons[i]
    this.leaders.push(lead)
  }
}

/**
 * @param {number} t
 * @return {number}
 */
TopVotedCandidate.prototype.q = function (t) {
  let lo = 0,
    hi = this.times.length - 1
  while (lo < hi) {
    const mid = (lo + hi + 1) >> 1
    if (this.times[mid] <= t) lo = mid
    else hi = mid - 1
  }
  return this.leaders[lo]
}

py

class TopVotedCandidate:
    def __init__(self, persons: List[int], times: List[int]):
        self.times = times
        self.leaders = []
        from collections import defaultdict
        votes = defaultdict(int)
        lead = -1
        for p in persons:
            votes[p] += 1
            if votes[p] >= votes[lead]:
                lead = p
            self.leaders.append(lead)

    def q(self, t: int) -> int:
        import bisect
        idx = bisect.bisect_right(self.times, t) - 1
        return self.leaders[idx]

• 时间复杂度：初始化 $O(n)$，查询 $O(\log n)$
• 空间复杂度：$O(n)$

算法思路：

• 初始化时预处理每个时刻的领先者
• 查询时二分查找时刻 t 对应的最后一次投票时刻